package leetcode.code0992;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution implements IDebug {

	public int subarraysWithKDistinct(int[] nums, int k) {
		if (k == 1) {
			return nums.length;
		}
		int k1 = find(nums, k);
		int k2 = find(nums, k - 1);
		return k1 - k2;
	}

	private int find(int[] nums, int k) {
		int len = nums.length;
		int[] hash = new int[len + 1];
		int kind = 0;
		int ans = 0;
		int l = 0;
		for (int r = 0; r < len; r++) {
			int num = nums[r];
			if (hash[num] == 0) {
				kind++;
			}
			hash[num]++;
			while (kind > k) {
				ans += r - l;
				int L = nums[l++];
				hash[L]--;
				if (hash[L] == 0) {
					kind--;
				}
			}
		}
		ans += (1 + len - l) * (len - l) / 2;
		return ans;
	}

	@Override
	public void debug4() {
		HelpDebug.compare(7, this.subarraysWithKDistinct(HelpDebug.str2array3("[1,2,1,2,3]"), 2));
		HelpDebug.compare(3, this.subarraysWithKDistinct(HelpDebug.str2array3("[1,2,1,3,4]"), 3));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
